package by2019;

import java.util.ArrayDeque;
import java.util.Comparator;
import java.util.Deque;
import java.util.PriorityQueue;

//给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。

public class 滑动窗口的最大值 {

	public static void main(String[] args) {
		int[] i = new int[] {1,3,-1,-3,5,3,6,7};
		maxSlidingWindowPro(i, 3);
	}
	
	//此方法维护了一个大顶堆和一个双端队列，效率太低
    public static int[] maxSlidingWindow(int[] nums, int k) {
    	
    	if(nums.length==0 || nums.length==1 || k==1)
    		return nums ;
    	
    	PriorityQueue<Integer> pque = new PriorityQueue<Integer>(new Comparator<Integer>() {

			@Override
			public int compare(Integer o1, Integer o2) {
				return o2-o1;
			}
		});

    	Deque<Integer> que = new ArrayDeque<Integer>();
    	int[] tem = new int[nums.length-k+1] ;
    	System.out.println(tem.length);
    	que.add(nums[0]) ;
    	pque.add(nums[0]) ;
    	int j = 0 ;
    	
    	for(int i=1; i<nums.length; i++) {
    		if(que.size()>=k) {
    			que.add(nums[i]) ;
    			pque.add(nums[i]);
    			pque.remove(que.removeFirst());
    		} else {
    			que.add(nums[i]);
    			pque.add(nums[i]) ;
    		}
    		System.out.println("双端队列： "+que);
    		System.out.println("大顶堆： "+pque);
    		
    		if(i<k-1)
    			continue ;
    		
    		tem[j] = pque.peek() ;
    		System.out.println("add to : "+pque.peek());
    		j++ ;
    	}
    	
    	System.out.println("最后返回的数组为：");
    	for(int i : tem )
    		System.out.print(i+" ");
    	
    	return tem ;
    }
    
    //加强版，去除了对双端队列的维护
    public static int[] maxSlidingWindowPro(int[] nums, int k) {
    	
    	if(nums.length==0 || nums.length==1 || k==1)
    		return nums ;
    	
    	PriorityQueue<Integer> pque = new PriorityQueue<Integer>(new Comparator<Integer>() {

			@Override
			public int compare(Integer o1, Integer o2) {
				return o2-o1;
			}
		});
    	
    	int[] tem = new int[nums.length-k+1] ;
    	int j = 1 ;
    	int m = k ;
    	
    	for(int i=0;i<k;i++) {
    		pque.add(nums[i]);
    		System.out.println(nums[i]+"进入前置队列");
    	}
    	System.out.println("前置双端队列为： "+pque);
    	
		tem[0] = pque.peek() ;
		System.out.println(tem[0]+" 进入结果数组");
    	
    	for(  ; m<nums.length; m++) {
    		
    		pque.add(nums[m]);
    		pque.remove(nums[j-1]);
    		System.out.println("双端队列为： "+pque);
    		tem[j] = pque.peek() ;
    		System.out.println(tem[j]+" 进入结果数组");
    		j++ ;
    	}
    	System.out.println("最终结果数组为： ");
    	for(int i : tem )
    		System.out.print(i+" ");
    	return tem ;
    }

}
